In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Bajtocja posiada rozbudowaną sieć autostrad. Każda autostrada łączy dwa miasta. Autostrady są płatne. Cena za przejazd autostradą zmienia się codziennie i może być różna w różne strony. Koszt przejazdu autostradą (w każdym kierunku) zmienia się liniowo. Inaczej mówiąc, istnieje stała (zależna od autostrady i kierunku) taka, że każdego następnego dnia cena zmienia się o (stała może być ujemna, wtedy cena maleje, lub równa 0, wtedy cena nie zmienia się, lub może być dodatnie, wtedy cena rośnie). Zmiana cen przejazdu autostradami następuje o północy.
Bajtazar mieszka w mieście . Pragnie odwiedzić znajomego, który mieszka w mieście . Chce więc przejechać z miasta do i wrócić tego samego dnia do miasta . Ponieważ jest oszczędny, to wybierze taki dzień, w którym będzie mógł jak najmniej zapłacić za przejazd autostradami. Musi jednak odwiedzić znajomego nie później niż dnia .
Sieć autostrad w Bajtocji jest na tyle rozbudowana, że z każdego miasta daje się dojechać do każdego innego. Pomiędzy każdymi dwoma miastami jest najwyżej jedno bezpośrednie połączenie. Bajtocja jest na tyle mała, że Bajtazar spokojnie zdąży przejechać do miasta i z powrotem w ciągu jednego dnia najtańszą trasą. Ponadto wiadomo, że w ciągu badanych dni cena przejazdu każdą autostradą będzie dodatnia.
Napisz program, który:
W pierwszym wierszu wejścia znajduje się pięć liczb całkowitych , , , , gdzie jest liczbą miast, liczbą autostrad, numerem miasta, w którym mieszka Bajtazar, numerem miasta, w którym mieszka jego znajomy, liczbą dni, w przeciągu których Bajtazar musi odwiedzić znajomego. Miasta są ponumerowane od do . Możesz założyć, że Bajtazar mieszka w innym mieście niż jego znajomy. W następnych wierszach znajdują się opisy kolejnych autostrad. Każdy wiersz zawiera sześć liczb całkowitych: . Liczby i to numery miast, które łączy autostrada. Liczby i oznaczają ceny przejazdu z miasta do oraz z do pierwszego dnia. Każdego kolejnego dnia pierwsza z tych cen zmienia się o , a druga o . Wiadomo, że podczas dni od do każda cena będzie dodatnia i nie większa niż .
W pierwszym i jedynym wierszu powinna się znajdować dokładnie jedna liczba całkowita - minimalny koszt dojechania z miasta do i z powrotem, w ciągu jednego z pierwszych dni.
4 4 1 4 3 1 2 5 -1 10 -1 3 2 12 2 7 2 3 4 8 -1 20 -3 1 4 27 -2 3 0poprawną odpowiedzią jest:
23
Na powyższym rysunku jedno połączenie między dwoma miastami narysowane jest jako para krawędzi, aby rozróżnić koszty w poszczególnych kierunkach. Para liczb przy każdej krawędzi oznacza odpowiednio koszt pierwszego dnia, oraz zmianę kosztu jaka następuje po każdym dniu. Jednym z optymalnych rozwiązań dla testu przykładowego jest przejechanie drugiego dnia trasy: kiedy koszt przejazdu wynosi .
Autor zadania: Paweł Parys.